package main.leetcode.clockin.September;

/**
 * 486. 预测赢家
 *
 * <p>给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，……
 * 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
 *
 * <p>给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
 *
 * <p>示例 1：<br>
 * 输入：[1, 5, 2] <br>
 * 输出：False <br>
 * 解释：一开始，玩家1可以从1和2中进行选择。 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者
 * 2 ）可选。 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。 因此，玩家 1 永远不会成为赢家，返回 False 。
 *
 * <p>示例 2：<br>
 * 输入：[1, 5, 233, 7] <br>
 * 输出：True <br>
 * 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。 最终，玩家 1（234 分）比玩家 2（12
 * 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
 *
 * <p>提示：<br>
 * 1 <= 给定的数组长度 <= 20. <br>
 * 数组里所有分数都为非负数且不会大于 10000000 。 <br>
 * 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。
 */
public class day1 {
    public static void main(String[] args) {
        System.out.println(new day1().PredictTheWinner(new int[] {1, 5, 2}));
        System.out.println(new day1().PredictTheWinner(new int[] {1, 5, 8, 4}));
        System.out.println(new day1().PredictTheWinner(new int[] {1, 5, 233, 7}));
    }

    /** 数学「博弈论」 + 动态规划（状态压缩） */
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        if (n < 3 || (n & 2) == 0) {
            return true;
        }
        // 定义 dp[i][j] 表示 作为先手，在 nums[i..j] 中可以获得的「相对分数」
        int[] dp = new int[n];
        // 初始化 dp[i][i]，当前只有一个数nums[i]时，作为先手，必得 nums[i] 分
        for (int i = 0; i < n; i++) {
            dp[i] = nums[i];
        }
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                // 当前玩家会选择最优的方案，使得自己的分数最大化
                // 以首部为例，作为先手，此轮拿下nums[i]分，再减去下一轮后手拿到的dp[i+1][j]分，即为此轮先手于后手的「净胜分」
                //                  |取首部                  |取尾部
                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[n - 1] >= 0;
    }

    //    /** 状态压缩 */
    //    public boolean PredictTheWinner(int[] nums) {
    //        int n = nums.length;
    //        if (n < 3) {
    //            return true;
    //        }
    //        // 定义 dp[i][j] 表示 作为先手，在 nums[i..j] 中可以获得的「相对分数」
    //        int[] dp = new int[n];
    //        // 初始化 dp[i][i]，当前只有一个数nums[i]时，作为先手，必得 nums[i] 分
    //        for (int i = 0; i < n; i++) {
    //            dp[i] = nums[i];
    //        }
    //        for (int i = n - 2; i >= 0; --i) {
    //            for (int j = i + 1; j < n; ++j) {
    //                // 当前玩家会选择最优的方案，使得自己的分数最大化
    //                // 以首部为例，作为先手，此轮拿下nums[i]分，再减去下一轮后手拿到的dp[i+1][j]分，即为此轮先手于后手的「净胜分」
    //                //                  |取首部                  |取尾部
    //                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
    //            }
    //        }
    //        return dp[n - 1] >= 0;
    //    }

    //    /** 动态规划 —— 二维 */
    //    public boolean PredictTheWinner(int[] nums) {
    //        int n = nums.length;
    //        if (n < 3) {
    //            return true;
    //        }
    //        // 定义 dp[i][j] 表示 作为先手，在 nums[i..j] 中可以获得的「相对分数」
    //        int[][] dp = new int[n][n];
    //        // 初始化 dp[i][i]，当前只有一个数nums[i]时，作为先手，必得 nums[i] 分
    //        for (int i = 0; i < n; i++) {
    //            dp[i][i] = nums[i];
    //        }
    //        for (int i = n - 2; i >= 0; --i) {
    //            for (int j = i + 1; j < n; ++j) {
    //                // 当前玩家会选择最优的方案，使得自己的分数最大化
    //                // 以首部为例，作为先手，此轮拿下nums[i]分，再减去下一轮后手拿到的dp[i+1][j]分，即为此轮先手于后手的「净胜分」
    //                //                  |取首部                  |取尾部
    //                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
    //            }
    //        }
    //        return dp[0][n - 1] >= 0;
    //    }

    //    /** 记忆化搜索 */
    //    public boolean PredictTheWinner(int[] nums) {
    //        int n = nums.length;
    //        if (n < 3) {
    //            return true;
    //        }
    //        int[][] memo = new int[n][n];
    //        for (int[] ints : memo) {
    //            Arrays.fill(ints, -1);
    //        }
    //        return memorize(0, n - 1, 1, nums, memo) >= 0;
    //    }
    //
    //    private int memorize(int i, int j, int multiplier, int[] nums, int[][] memo) {
    //        if (i == j) {
    //            return nums[i];
    //        }
    //        if (memo[i][j] > -1) {
    //            return memo[i][j];
    //        }
    //        int left = nums[i] * multiplier + memorize(i + 1, j, -multiplier, nums, memo);
    //        int right = nums[j] * multiplier + memorize(i, j - 1, -multiplier, nums, memo);
    //        return memo[i][j] = multiplier == 1 ? Math.max(left, right) : Math.min(left, right);
    //    }

    //    /** dfs */
    //    public boolean PredictTheWinner(int[] nums) {
    //        int n = nums.length;
    //        if (n < 3) {
    //            return true;
    //        }
    //        return dfs(0, n - 1, 1, nums) >= 0;
    //    }
    //
    //    private int dfs(int l, int r, int multiplier, int[] nums) {
    //        if (l == r) {
    //            return nums[l] * multiplier;
    //        }
    //        int left = nums[l] * multiplier + dfs(l + 1, r, -multiplier, nums);
    //        int right = nums[r] * multiplier + dfs(l, r - 1, -multiplier, nums);
    //        return multiplier == 1 ? Math.max(left, right) : Math.min(left, right);
    //    }

    //    /** 回溯 */
    //    public boolean PredictTheWinner(int[] nums) {
    //        int n = nums.length;
    //        if (n < 3) {
    //            return true;
    //        }
    //        return backTrack(0, n - 1, true, 0, 0, nums);
    //    }
    //
    //    private boolean backTrack(int start, int end, boolean player, int sum1, int sum2, int[]
    // nums) {
    //        if (start > end) {
    //            return sum1 >= sum2;
    //        }
    //        if (player) {
    //            // 玩家1任意选一端，只要有能赢的情况，玩家1获胜
    //            return backTrack(start + 1, end, false, sum1 + nums[start], sum2, nums)
    //                    || backTrack(start, end - 1, false, sum1 + nums[end], sum2, nums);
    //        } else {
    //            // 玩家2需要选取两端都有能赢的情况，玩家2才能获胜
    //            return backTrack(start + 1, end, true, sum1, sum2 + nums[start], nums)
    //                    && backTrack(start, end - 1, true, sum1, sum2 + nums[end], nums);
    //        }
    //    }

}
